package a00_LeetCode.Stack;

/**
 * @Author quan
 * @Description 判断是否是有效的括号
 * @Date 2023/3/22 11:44
 */

import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 */

public class Num20_IsValidString {
    public boolean isValid(String s) {
        //创建栈
        Stack<Character> stack = new Stack<>();
        //给出来的是字符串类型，要先转为字符
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //让获取到的字符入栈：判断是不是左括号，如果是左括号的话才能入栈，直到遇见第一个右括号为止
            if (ch=='[' || ch=='{' || ch=='('){
                stack.push(ch);
            }else{
                //如果此时的符号是右括号，直接返回false
                if(stack.isEmpty()){
                    return false;
                }else{
                    //如果判断的是右括号:这里要写pop将栈顶的元素弹出，之前写的是peek，一直都是最上方的栈顶元素没有变化
                    char temp = stack.pop();
                    if(ch == ']' && (temp=='(' || temp == '{')){
                        return false;
                    }
                    if(ch == ')' && (temp=='[' || temp == '{')){
                        return false;
                    }
                    if(ch == '}' && (temp=='(' || temp == '[')){
                        return false;
                    }
                }
            }
        }
        //这里不能直接返回true，如果只有一个左括号的情况 [，for循环执行完走到这里是要判断栈中是否为空的。
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}
